package m202401.d08;

import java.util.Arrays;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/1/8 10:09
 */
//105. 从前序与中序遍历序列构造二叉树
public class Q105 {

    public static void main(String[] args) {
        new Q105().buildTree(new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7});
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preEnd == preStart || inStart == inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = findIndex(preorder[preStart], inorder);
        root.left = buildTree(preorder, preStart + 1, preStart + (index - inStart)+1, inorder, inStart, index);
        root.right = buildTree(preorder, preStart + (index - inStart)+1, preEnd, inorder, index + 1, inEnd);
        return root;
    }

    public int findIndex(int target, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (target == inorder[i]) {
                return i;
            }
        }
        return -1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
